#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_s {
	long data;
	struct node_s *left;
	struct node_s *right;
	int max_left;
	int max_right;
} node_t;

void insert_tree(node_t **root, long data)
{
	node_t *new, *p;

	new = (node_t *)malloc(sizeof(node_t));
	if (new == NULL) {
		printf("malloc for node failed\n");
		return;
	}
	memset(new, 0, sizeof(node_t));
	new->data = data;

	if (NULL == *root) {
		*root = new;
		return;
	}

	p = *root; 
	while(1) {
		if (data >= p->data) {
			if (p->right)
				p = p->right;
			else {
				p->right = new;
				break;
			}
		} else {
			if (p->left)
				p = p->left;
			else {
				p->left = new;
				break;
			}
		}
	}
}

void create_tree(node_t **root, int n)
{
	long ran_a, ran_b, data;
	int i;

	for (i = 0; i < n; i ++) {
		ran_a = random();
		ran_b = random();
		data = ran_a + (ran_a - ran_b) + ((ran_a + ran_b) >> 1);
		data %= 100;
		printf("%d times:insert:%ld\n", i, data);
		insert_tree(root, data);
	}
}

void pre_scan_tree(node_t *node)
{
	printf("%ld\t", node->data);
	if (node->left)
		pre_scan_tree(node->left);
	if(node->right)
		pre_scan_tree(node->right);
}

void mid_scan_tree(node_t *node)
{
	if (node->left)
		mid_scan_tree(node->left);
	printf("%ld\t", node->data);
	if(node->right)
		mid_scan_tree(node->right);
}

void back_scan_tree(node_t *node)
{
	printf("%ld\t", node->data);
	if (node->left)
		back_scan_tree(node->left);
	if(node->right)
		back_scan_tree(node->right);
}


#define MAX 64

typedef struct {
	node_t *arr[MAX];
	int ps;
} stack_t;
stack_t stack[1];

void  init_stack(stack_t *stack)
{
	memset(stack->arr, 0, sizeof(node_t *) * MAX);
	stack->ps = 0;
}

int push(stack_t *q, node_t *new)
{
	if (q->ps == MAX)
		return -1;
	q->arr[q->ps] = new;
	q->ps ++;

	return 0;
}

node_t* pop(stack_t *q)
{
	node_t *ret = NULL;

	if (q->ps != 0) {
		q->ps --;
		ret = q->arr[q->ps];
	}
	
	return ret;
}

node_t* top(stack_t *q)
{
	node_t *ret = NULL;
	if (q->ps != 0) 
		ret = q->arr[q->ps - 1];

	return ret;
}

int empty(stack_t *q)
{
	if (q->ps != 0)
		return 0;
	else 
		return 1;
}


void pre_scan_tree_2(node_t *root)
{
	stack_t stack[1];
	node_t *node = root;

	init_stack(stack);
	
	while (node) {
		printf("%ld\t", node->data);
		if (node->right)
			push(stack, node->right);
		if (node->left)
			node = node->left;
		else 
			node = pop(stack);

	}
}

void mid_scan_tree_2(node_t *root)
{
	stack_t stack[1];
	node_t *node = root;

	init_stack(stack);
	
	while (node) {
		if (node->left) {
			push(stack, node);
			node = node->left;
			continue;
		}
		printf("%ld\t", node->data);
		
		if (node->right) {
			node = node->right;
			continue;
		}

		node = pop(stack);
		if (node) {
			printf("%ld\t", node->data);
			node = node->right;
		}
	}
}

#if 0
/* two stack
 * stack_a: store the node whose right never scaned
 * stack_b: store the node whosw right being scaned
 */
void back_scan_tree_2(node_t *root)
{
	stack_t stack_a[1], stack_b[1];
	node_t *node = root, tmp = NULL;

	init_stack(stack_a);
	init_stack(stack_b);
	
	while (node) {
		if (node->left) {
			push(stack_a, node);
			node = node->left;
			continue;
		}
		if (node->right) {
			push(stack_b, node);
			node = node->right;
			continue;
		}
		printf("%ld\t", node->data);


	}
}
#endif

void post_scan_tree(node_t *root)
{
	node_t *pre = NULL, *cur = root;
	stack_t s[1];

	init_stack(s);
	
	while (cur || !empty(s)) {
		while (cur) {
			push(s, cur);
			cur = cur->left;
		}

		cur = top(s);

		if (!cur->right || cur->right == pre) {
			printf("%ld\t", cur->data);
			pop(s);
			pre = cur;
			cur = NULL;
		} else {
			cur = cur->right;
		}
	}
}

void prev_scan_tree_1(node_t *root)
{
	stack_t s[1];
	init_stack(s);

	while (root || !empty(s)) {
		if (root) {
			printf("%ld\t", root->data);
			push(s, root);
			root = root->left;
		} else {
			root = pop(s);
			root = root->right;
		}
	}
}

void prev_scan_tree_2(node_t *root)
{
	stack_t s[1];
	init_stack(s);

	push(s, root);
	while(!empty(s)) {
		root = pop(s);
		printf("%ld\t", root->data);
		if (root->right) push(s, root->right);
		if (root->left) push(s, root->left);
	}
}

void in_scan_tree(node_t *root)
{
	stack_t s[1];
	init_stack(s);

	while(root || !empty(s)) {
		if (root) {
			push(s, root);
			root = root->left;
		} else {
			root = pop(s);
			printf("%ld\t", root->data);
			root = root->right;
		}
	}
}

int main()
{
	int n = 8;
	node_t *root = NULL;

	create_tree(&root, n);
#if 0
	printf("\n");
	pre_scan_tree(root);
	printf("\n");
	mid_scan_tree(root);
#endif
	//printf("\n");
	//back_scan_tree(root);

#if 0
	printf("\n no recursion pre:\n");
	pre_scan_tree_2(root);

	printf("\n no recursion mid:\n");
	mid_scan_tree_2(root);

#endif
	printf("\n no recursion back:\n");
	//back_scan_tree_2(root);
	post_scan_tree(root);
	printf("\n");
	prev_scan_tree_1(root);
	printf("\n");
	prev_scan_tree_2(root);
	printf("\n");
	in_scan_tree(root);
	printf("\n");
	return 0;
}

